package com.SuanFa.jiangdongqi;

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
     public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;//记录腐烂时间
        int sum = 0;//记录新鲜水果的个数
        Queue<int[]> queue = new ArrayDeque<>();
        int[][]dx= {{1,0},{-1,0},{0,1},{0,-1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2){
                    queue.add(new int[]{i,j,0});//i，j分别代表的是水果的横纵坐标 最后的值代表的是时间t=0，初始值为0；
                }else if (grid[i][j] == 1 ){
                    sum++;
                }
            }
        }
        while(!queue.isEmpty()){
            int[] poll = queue.poll();//提出队列中第一个烂水果
            int x = poll[0];
            int y = poll[1];
            int t = poll[2];
            ans = Math.max(ans, t);
            for (int i = 0; i < dx.length; i++) {
                int xx = x+dx[i][0];
                int yy = y+dx[i][1];
                if (xx>=0&&xx<m&&yy>=0&&yy<n&&grid[xx][yy]==1){
                    sum --;
                    grid[xx][yy]=0;
                    queue.add(new int[]{xx,yy,t+1});
                }
            }
        }
        if (sum>0){
            return -1;//有的水果没贴近，所以有水果没有被感染腐烂
        }
        return ans;
    }
}